package alo.p3.work;

import alo.p3.ListNode;

/*
* 给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。

示例1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
*/
public class rotateRight {

    //构建一个循环链表，在移动n-k%n-1位，指向尾部
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if (head == null || head.getNext() == null) return head;
            int n = 1;
            ListNode c1 = head;
            while (c1.getNext() != null) {
                n++;
                c1 = c1.getNext();
            }
            c1.setNext(head);
            for (int i = 0; i < n - k % n - 1; i++) {
                head = head.getNext();
            }
            c1 = head.getNext();
            head.setNext(null);
            return c1;
        }
    }
}
